import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

/*
题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
字符可能有重复！
方法：
使用回溯的方法进行尝试，用set去除相同字符交换的情况
 */
public class E38 {
    public static void main(String[] args) {
        String str = "abc";
        ArrayList<String> res = Permutation(str);
        System.out.println(res);
    }
    public static ArrayList<String> Permutation(String str) {
           ArrayList<String> list = new ArrayList<>();
           if(str != null && str.length() > 0){
               helper(str.toCharArray(), 0, list);
               Collections.sort(list);
           }
           return list;
    }

    public static void helper(char[] chars, int index, ArrayList<String> list){
        if(index == chars.length - 1){
            list.add(String.valueOf(chars));
        }
        else{
            Set<Character> charSet = new HashSet<Character>();
            for(int i = index; i < chars.length; i++){
                if(index == i || !charSet.contains(chars[i])){
                    charSet.add(chars[i]);
                    swap(chars, i,index);
                    helper(chars, index + 1, list);
                    swap(chars, index, i);
                }
            }
        }
    }

    private static void swap(char[] cs, int i, int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}
